package com.arron.algorithm.leetcodetop100.贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 划分字母区间 {


    /**
     *  解法一 贪心+双指针
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {

        int[] lastIndexArrays = new int[26];

        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            lastIndexArrays[chars[i]-'a'] = i;
        }

        int start =0;
        int end = 0;

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {

            end = Math.max(lastIndexArrays[chars[i]-'a'],end);

            if (i == end){
                res.add(end-start+1);
                start = end +1;
                end = 0;
            }


        }
        return res;
    }


    /**
     *  解法二 ： 类似无重叠区间解法
     * @see 无重叠区间_贪心
     * @param s
     * @return
     */
    public  List<Integer> partitionLabels_02(String s) {
        int[][] partitions = findPartitions(s);
        List<Integer> res = new ArrayList<>();

        //按照左端点排序
        Arrays.sort(partitions, (a, b) -> a[0]-b[0]);
        int right = partitions[0][1];
        int left = 0;
        for (int i = 0; i < partitions.length; i++) {
            if (partitions[i][0] > right) {
                //左边界大于右边界即可纪委一次分割
                res.add(right - left + 1);
                left = partitions[i][0];
            }
            right = Math.max(right, partitions[i][1]);

        }
        //最后一个区间
        res.add(right - left + 1);
        return res;

    }

    /**
     * 记录 将每个字母出现的开始出现位置和最后一次出现的位置
     * @param s
     * @return
     */
    public  int[][] findPartitions(String s) {
        List<Integer> temp = new ArrayList<>();
        int[][] hash = new int[26][2];//26个字母2列 表示该字母对应的区间

        for (int i = 0; i < s.length(); i++) {
            //更新字符c对应的位置i
            char c = s.charAt(i);
            if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;

            hash[c - 'a'][1] = i;

            //第一个元素区别对待一下
            hash[s.charAt(0) - 'a'][0] = 0;
        }


        List<List<Integer>> h = new LinkedList<>();
        //组装区间
        for (int i = 0; i < 26; i++) {
            //if (hash[i][0] != hash[i][1]) {
            temp.clear();
            temp.add(hash[i][0]);
            temp.add(hash[i][1]);
            //System.out.println(temp);
            h.add(new ArrayList<>(temp));
            // }
        }
        // System.out.println(h);
        // System.out.println(h.size());
        int[][] res = new int[h.size()][2];
        for (int i = 0; i < h.size(); i++) {
            List<Integer> list = h.get(i);
            res[i][0] =  list.get(0);
            res[i][1] =  list.get(1);
        }

        return res;

    }





    public static void main(String[] args) {
        划分字母区间 as = new 划分字母区间();
        String s = "ababcbacadefegdehijhklij";


        as.partitionLabels(s);
    }

}
